package ljl.codetop300;

/**
 * 输入：amount = 3, coins = [2]
 * 输出：0
 * 解释：只用面额 2 的硬币不能凑成总金额 3 。
 *
 * 这个题居然得用 dp，我是不会做
 */
public class _518_coin_change_2 {

  /**
   * 看着很短，怎么感觉不是太好理解？
   */
  static class off {
    public int change(int amount, int[] coins) {
      int[] dp = new int[amount + 1];
      dp[0] = 1;
      // 这个循环让人非常费解
      for (int coin : coins) {
        // 从 coin 到 amount，每个值加上去掉 coin 的上一个值等于多少
        for (int i = coin; i <= amount; i++) {
          dp[i] += dp[i - coin];
        }
      }
      return dp[amount];
    }
  }

  /**
   */
  static class tr {
    public int change(int amount, int[] coins) {
      int[] dp = new int[amount + 1];
      dp[0] = 1;
      for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
          dp[i] += dp[i - coin];
        }
      }
      return dp[amount];
    }
  }
}
